package com.xiaolin.structure.queue.monotone;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName MonotoneIncreaseQueue
 * @Description 单调队列-单调递减
 * @Detail      特点：
 *                  1、每个元素最多进队一次，出队一次
 *               操作：
 *                  1、元素从队尾入队
 *                  2、队尾元素如果小于等于要入队的元素，将队尾元素移除
 *                  3、以此类推，直到队列为空或者队尾元素大于要入队的元素
 * @Author MyPC
 * @Date 2020/12/13
 * @Version 1.0
 */
public class MonotoneDecreaseQueue {
    public static void main(String[] args) {
        int[] arr=new int[]{3,4,2,6,4,5,2,3};
        Deque<Integer> deque=new LinkedList<>();
        for (int i=0;i<arr.length;i++){
            while (deque.size()>0 && arr[deque.peekLast()]<=arr[i]){
                deque.pollLast();
            }
            deque.addLast(i);
        }
        for (Integer integer : deque) {
            System.out.println(arr[integer]);
        }
    }
}
